import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.ArrayList;
import java.util.Collections;

public class LIST {
    //牛客top101——链表
    /**
     * 反转链表
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        ListNode pHead = null;
        while (head!=null){
            ListNode cur = head.next;
            head.next = pHead;
            pHead = head;
            head = cur;
        }
        return pHead;
    }
    /**
     * 链表内指定区间反转
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode pHead = new ListNode(-1);
        pHead.next = head;
        ListNode pre = pHead;
        for (int i = 0; i < m-1; i++) {
            pre = pre.next;
        }
        ListNode right = pre;
        for (int i = 0; i < n-m+1; i++) {
            right = right.next;
        }

        ListNode left = pre.next;
        ListNode cur = right.next;

        pre.next = null;
        right.next = null;


        ReverseList(left);

        pre.next = right;
        left.next = cur;
        return pHead.next;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        //考虑分完和分不完的情况
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null){
                return head;
            }
            tail = tail.next;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=tail){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        head.next = reverseKGroup(tail,k);
        return pre;
    }
    /**
     * 合并两个排序的链表
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        if (pHead1==null || pHead2==null){
            return pHead1!=null?pHead1:pHead2;
        }

        if (pHead1.val<=pHead2.val){
            pHead1.next = Merge(pHead1.next,pHead2);
            return pHead1;
        }else {
            pHead2.next=Merge(pHead1,pHead2.next);
            return pHead2;
        }
    }

    /**
     * 合并k个已排序的链表
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    //排序K个已排序的链表
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return divideMerge(lists,0,lists.size()-1);
    }
    ListNode divideMerge(ArrayList<ListNode> lists,int left,int right){
        if (left>right){
            return null;
        }else if (left == right){
            return lists.get(left);
        }
        int mid = (left+right)/2;
        return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }


    /**
     * 判断链表中是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        //快慢指针
        if (head == null){
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }

    /**
     * 链表中环的入口结点
     * @param pHead
     * @return
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //先判断是否有环，再找环的入口
       ListNode slow = has(pHead);
       if (slow == null){
           return null;
       }

       ListNode fast = pHead;
       while (fast!=slow){
           fast = fast.next;
           slow = slow.next;
       }
       return slow;
    }
    private ListNode has(ListNode Head){
        if (Head == null){
            return null;
        }
        ListNode fast = Head;
        ListNode slow = Head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return slow;
            }
        }
        return null;
    }

    /**
     *链表中倒数最后k个结点
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
       //双指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        if (pHead == null){
            return null;
        }
        for (int i = 0; i < k; i++) {
            if (fast != null){
                fast = fast.next;
            }else {
                return slow = null;
            }

        }

        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    /**
     * 删除链表的倒数第n个结点
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        //双指针
        ListNode fast = head;
        ListNode slow = head;
        if (head == null || n == 0){
            return head;
        }
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        if (fast == null){
            return head.next;
        }
        while (fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return head;
    }


    /**
     * 两个链表的第一个公共结点
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        while (l1!=l2){
            l1 = (l1==null)?pHead2:l1.next;
            l2 = (l2 == null)?pHead1:l2.next;
        }
        return l1;
    }


    /**
     * 链表相加（二）
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        if (head1==null){
            return head2;
        }
        if (head2==null){
            return head1;
        }

        //反转两个链表
        head1=ReverseList(head1);
        head2=ReverseList(head2);
        //添加链表头
        ListNode res = new ListNode(-1);
        ListNode head = res;
        //是否进位，进位标识符
        int carry = 0;
        //只要某个链表还有元素或者进位还存在
        while (head1!=null||head2!=null||carry!=0){
            //链表不为空取链表的值
            int val1 = head1==null?0:head1.val;
            int val2 = head2==null?0: head2.val;
            //相加
            int temp = val1+val2+carry;
            //进位
            carry = temp/10;
            temp %= 10;
            //添加元素
            head.next=new ListNode(temp);
            head = head.next;
            //移动到下一个的位置上
            if (head1!=null){
                head1=head1.next;
            }
            if (head2!=null){
                head2=head2.next;
            }
        }
        return ReverseList(res.next);
    }

    /**
     * 单链表的排序
     * @param  phead1 ListNode类 the head node
     * @return ListNode类
     */
    ListNode merge(ListNode phead1,ListNode phead2){
        if(phead1==null)return phead2;
        if(phead2==null)return phead1;

        ListNode head=new ListNode(0);
        ListNode cur=head;
        while(phead1!=null&&phead2!=null){
            if(phead1.val<=phead2.val){
                cur.next=phead1;
                phead1=phead1.next;
            }else{
                cur.next=phead2;
                phead2=phead2.next;
            }cur=cur.next;
        }
        if(phead1!=null){
            cur.next=phead1;
        }else cur.next=phead2;
        return head.next;
    }
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head==null||head.next==null){
            return head;
        }
        ListNode left=head;
        ListNode mid=head.next;
        ListNode right=head.next.next;
        while(right!=null&&right.next!=null){
            left=left.next;
            mid=mid.next;
            right=right.next.next;
        }
        left.next=null;
        return merge(sortInList(head),sortInList(mid));

    }
    /**
     * 判断一个链表是否为回文结构
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        ArrayList<Integer> nums = new ArrayList();
        //将链表元素取出一次放入数组
        while(head != null){
            nums.add(head.val);
            head = head.next;
        }
        ArrayList<Integer> temp = new ArrayList();
        temp = (ArrayList<Integer>) nums.clone();
        //准备一个数组承接翻转之后的数组
        Collections.reverse(temp);
        for(int i = 0; i < nums.size(); i++){
            int x = nums.get(i);
            int y = temp.get(i);
            //正向遍历与反向遍历相同
            if(x != y)
                return false;
        }
        return true;
    }


    /**
     * 删除有序链表中重复的元素-1
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates1 (ListNode head) {
        if (head == null){
            return null;
        }
        ListNode cur = head;
        while (cur!= null && cur.next!=null){
            if (cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return head;
    }


    /**
     * 链表的奇偶重排
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        //如果链表为空，不用重排
        if(head == null)
            return head;
        //even开头指向第二个节点，可能为空
        ListNode even = head.next;
        //odd开头指向第一个节点
        ListNode odd = head;
        //指向even开头
        ListNode evenHead = even;
        while(even != null && even.next != null){
            //odd连接even的后一个，即奇数位
            odd.next = even.next;
            //odd进入后一个奇数位
            odd = odd.next;
            //even连接后一个奇数的后一位，即偶数位
            even.next = odd.next;
            //even进入后一个偶数位
            even = even.next;
        }
        //even整体接在odd后面
        odd.next = evenHead;
        return head;
    }

    /**
     * 删除有序链表中重复的元素Ⅱ
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates2 (ListNode head) {
        if (head == null){
            return null;
        }
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode cur = res;
        while (cur.next!=null && cur.next.next!=null){
            if (cur.next.val==cur.next.next.val){
                int temp = cur.next.val;
                while (cur.next!=null && cur.next.val==temp){
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return res.next;
    }


}
